package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 * https://leetcode-cn.com/problems/partition-equal-subset-sum/
 * @version 1.0
 * @date 2021/11/20 15:34
 * @see findTargetSumWays
 * @see findTargetSumWays1
 */
public class canPartition {

    public static void main(String[] args) {

        System.out.println(canPartition(new int[]{1, 5, 11, 5}));
        System.out.println(canPartition1(new int[]{1, 5, 11, 5}));
        System.out.println(canPartition2(new int[]{1, 5, 11, 5}));
        System.out.println(canPartition4(new int[]{1, 5, 11, 5}));
    }

    // 经典01背包问题
    // 动态规划状态定义：boolean[i][j] dp, dp[i][j] 表示nums的前i个元素的和 能否为 j，boolean[nums.length + 1][target + 1]，二维矩阵有0行，0列
    // 动态规划初始值 ： dp[0][0] = true, nums 的前0个元素和 为 0
    // 动态规划转移方程：dp[i + 1][j] = dp[i][j] || dp[i][j - nums[i]]; 前提 j >= nums[i]
    // 优化初始值，更符合背包问题的二维矩阵
    static boolean canPartition1(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 奇数 或者 数组长度不足2
        if ((sum & 1) == 1 || nums.length <= 1) {
            return false;
        }
        int target = sum / 2;
        // dp[i][j] 前 i个元素的和 能否为 j
        boolean[][] dp = new boolean[nums.length + 1][target + 1];
        dp[0][0] = true;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j <= target; j++) {
                if (j >= nums[i]) {
                    dp[i + 1][j] = dp[i][j] || dp[i][j - nums[i]];
                } else {
                    dp[i + 1][j] = dp[i][j];
                }
                // 找到目标和，提前结束
                if (dp[i + 1][target]) return true;
            }
        }
        return dp[nums.length][target];
    }

    // 逆向枚举 优化空间复杂度
    // 空间复杂度优化：通过上面的canPartition1 我们可以知道，下一行的值只跟上一行的值相关
    // 并且 某个元素的值 之和上一行的左边元素相关，所以我们可以先遍历右边，先动态转换右边的元素
    static boolean canPartition2(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 奇数 或者 数组长度不足2
        if ((sum & 1) == 1 || nums.length <= 1) {
            return false;
        }
        int target = sum / 2;
        // dp[j] 前 i个元素的和 能否为 j
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        // 正确解法：01背包
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= 0; j--) {
                if (j >= nums[i]) {
                    dp[j] = dp[j] || dp[j - nums[i]];
                }
            }
            if (dp[target]) return true;
        }
        return dp[target];
    }

    // 转化成目标和为0 的问题，提交LeetCode 时间复杂度爆炸 O(2^n)
    static boolean canPartition4(int[] nums) {
        int targetSumWays = findTargetSumWays.findTargetSumWays(nums, 0);
        return targetSumWays > 0 ? true : false;
    }

    // LeetCode 官方解答，质量不高，不要看
    // nums.length 必须大于 1
    // nums 之和sum 必须为偶数
    // 从 nums 中选 数字（每个数字只能选择一次，选择或不选择） 组成 sum/2. 经典的 01背包问题
    static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 奇数 或者 数组长度不足2
        if ((sum & 1) == 1 || nums.length <= 1) {
            return false;
        }
        int target = sum / 2;
        // dp[i][j] 前 i个元素的和 能否为 j
        boolean[][] dp = new boolean[nums.length][target + 1];
        if (nums[0] <= target) {
            dp[0][nums[0]] = true;
        }
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= target; j++) {
                if (nums[i] == j) {
                    dp[i][j] = true;
                    continue;
                }
                if (j < nums[i]) {
                    dp[i][j] = dp[i - 1][j];
                }
                if (j > nums[i]) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
            }
        }
        return dp[nums.length - 1][target];
    }
}
